#include <stdio.h>
#include <limits.h>


#define MAX(a, b) ((a) > (b) ? (a): (b))

// greedy
int maxSubArray3(int *nums, int numsSize)
{
    int maxinum = INT_MIN;
    int count = 0;

    for (int i = 0; i < numsSize; i++) {
        count += nums[i];
        // 贪心，只要和变成负数了，立马丢弃
        maxinum = MAX(count, maxinum);
        if (count < 0)
            count = 0;
    }
    return maxinum;
}

// DP
int maxSubArray2(int* nums, int numsSize)
{
    int sum = 0;
    int max_last = nums[0];
    int maxinum = max_last;
    for (int i = 1; i < numsSize; i++) {
        if (max_last + nums[i] < nums[i])
            max_last = nums[i];
        else
            max_last = max_last + nums[i];
        maxinum = MAX(maxinum, max_last);
    }
    return maxinum;
}


// 复杂度O(n^2), 不能ac
int maxSubArray(int* nums, int numsSize)
{
    int maxinum = INT_MIN;
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        if (i > 0 && nums[i] < nums[i-1])
            continue;
        sum = nums[i];
        maxinum = MAX(maxinum, sum);
        for (int j = i+1; j < numsSize; j++) {
            sum += nums[j];
            maxinum = MAX(maxinum, sum);   
        }
    }
    return maxinum;
}

int main(void)
{
    printf("#53. 最大子数组和\n");
    printf("https://leetcode.cn/problems/maximum-subarray/description/\n");
    int nums[] = {-2,1,-3,4,-1,2,1,-5,4};
    //int nums[] = {-2};
    int ret = maxSubArray(nums, sizeof(nums)/sizeof(int));
    printf("ret : %d\n", ret);

    ret = maxSubArray2(nums, sizeof(nums)/sizeof(int));
    printf("ret : %d\n", ret);
    ret = maxSubArray3(nums, sizeof(nums)/sizeof(int));
    printf("ret : %d\n", ret);
}

